public class BinarySearchTree
{
    protected BinaryNode root;

    
    /* constructor */

    public BinarySearchTree( )
    {
        root = null;
    }


    /* insert */

    public void insert( Comparable x )
    {
        root = insert( x, root );
    }


    protected BinaryNode insert( Comparable x, BinaryNode t )
    {
        if( t == null )
            t = new BinaryNode( x );
        else if( x.compareTo( t.element ) < 0 )
            t.left = insert( x, t.left );
        else if( x.compareTo( t.element ) > 0 )
            t.right = insert( x, t.right );
        else
            throw new DuplicateItemException( x.toString( ) );
        return t;
    }


    /* find */

    public Comparable find( Comparable x )
    {
        return elementAt( find( x, root ) );
    }


    private Comparable elementAt( BinaryNode t )
    {
        return t == null ? null : t.element;
    }


    private BinaryNode find( Comparable x, BinaryNode t )
    {
        while( t != null )
        {
            if( x.compareTo( t.element ) < 0 )
                t = t.left;
            else if( x.compareTo( t.element ) > 0 )
                t = t.right;
            else
                return t;    // Match
        }
        
        return null;         // Not found
    }


    /* findMax */

    public Comparable findMax( )
    {
        return elementAt( findMax( root ) );
    }


    private BinaryNode findMax( BinaryNode t )
    {
        if( t != null )
            while( t.right != null )
                t = t.right;

        return t;
    }


    /* findMin */

    public Comparable findMin( )
    {
        return elementAt( findMin( root ) );
    }


    protected BinaryNode findMin( BinaryNode t )
    {
        if( t != null )
            while( t.left != null )
                t = t.left;

        return t;
    }


    /* removeMin */

    public void removeMin( )
    {
        if( root == null )
            throw new ItemNotFoundException( );

        root = removeMin( root );
    }


    protected BinaryNode removeMin( BinaryNode t )
    {
        if( t.left != null )
        {
            t.left = removeMin( t.left );
            return t;
        }
        else
            return t.right;
    }    


    /* remove */

    public void remove( Comparable x )
    {
        root = remove( x, root );
    }


    protected BinaryNode remove( Comparable x, BinaryNode t )
    {
        if( t == null )
            throw new ItemNotFoundException( x.toString( ) );
        if( x.compareTo( t.element ) < 0 )
            t.left = remove( x, t.left );
        else if( x.compareTo( t.element ) > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = removeMin( t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }


    /* makeEmpty */

    public void makeEmpty( )
    {
        root = null;
    }


    /* isEmpty */

    public boolean isEmpty( )
    {
        return root == null;
    }

}